package com.mlh.skill;

import com.mlh.sort.InsertionSort;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

/**
 * @author 缪林辉
 * @date 2024/7/2 11:30
 * @DESCRIPTION
 */
//给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
// 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
public class 只出现一次的数字 {
    public int method1(int[] nums) {
        HashSet<Integer>set=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])){
                set.remove(nums[i]);
            }else{
                set.add(nums[i]);
            }
        }
        Iterator<Integer> iterator = set.iterator();
        return iterator.next();
    }
    //力扣答案
    //异或运算有以下三个性质。
    // 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
    // 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
    // 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
    //因此将元素逐一进行位运算，最终的结果就是答案
    public int method2(int[] nums) {
        int res=0;
        for (int i = 0; i < nums.length; i++) {
            res^=nums[i];
        }
        return res;
    }

    public int practice(int[] nums){
        int res=nums[0];
        for (int i = 1; i <nums.length ; i++) {
            res^=nums[i];
        }
        return res;
    }

    public int practice2(int[] nums){
        int a=nums[0];
        for (int i = 1; i < nums.length; i++) {
            a^=nums[i];
        }
        return a;
    }
}
